﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm_2.Middle_2049_CountHighestScoreNodes
{
    class MainProject
    {
        static void Main(string[] args)
        {
            Console.WriteLine(CountHighestScoreNodes(new int[] { -1, 2, 0, 2, 0 }));
            Console.ReadKey();
        }
        public static int CountHighestScoreNodes(int[] parents)
        {
            #region 有问题，未考虑乘积最大不一定是1*7这种
            //观察可得规律最高分数为parents.Length-1,且必有最高分数
            //因为叶子结点满足这个条件，所以转换成有多少叶子结点
            //但是考虑到根节点，所以继续转换成，只有一个分支得结点
            //Dictionary<int, int> dic = new Dictionary<int, int>();
            //dic.Add(0, 0);
            //for (int i = 1; i < parents.Length; i++) dic.Add(i, 1);
            //for (int i = 0; i < parents.Length; i++) if (dic.ContainsKey(parents[i])) dic[parents[i]]++;
            //int num = 0;
            //foreach (var item in dic.Values) if (item == 1) num++;
            //return num;
            #endregion

            //递归要学到家啊
            //DFS(node) = 包含自身的子结点的个数

            //预处理
            Dictionary<int, List<int>> dic = new Dictionary<int, List<int>>();
            for (int i = 0; i < parents.Length; i++) dic.Add(i, new List<int>());
            for (int i = 0; i < parents.Length; i++) if (dic.ContainsKey(parents[i])) dic[parents[i]].Add(i);

            int n = parents.Length;
            long maxScore = -1;
            int maxScoreNum = 0;
            DFS(0, n, dic, ref maxScore, ref maxScoreNum);
            return maxScoreNum;
        }

        private static int DFS(int node, int n, Dictionary<int, List<int>> dic, ref long maxScore, ref int maxScoreNum)
        {
            long score = 1;
            int size = n - 1;
            for (int i = 0; i < dic[node].Count; i++)
            {
                int t = DFS(dic[node][i], n, dic, ref maxScore, ref maxScoreNum);
                score *= t;
                size -= t;
            }
            if (node != 0)
            {
                score *= (size);
            }
            if (score > maxScore)
            {
                maxScore = score;
                maxScoreNum = 1;
            }
            else if (score == maxScore)
            {
                maxScoreNum++;
            }

            return n - size;
        }
    }
}
